package com.lw.leetcode.linked.c;


import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * c
 * linked
 * 460. LFU 缓存
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/8 16:16
 */
public class LFUCache {


    public static void main(String[] args) {

        int k = 3;

        LFUCache test = new LFUCache(k);

        // 2,1,2,-1,2,1,4
        test.put(2, 2);
        test.put(1, 1);
        System.out.println(test.get(2));
        System.out.println(test.get(1));
        System.out.println(test.get(2));
        test.put(3, 3);
        test.put(4, 4);
        System.out.println(test.get(3));
        System.out.println(test.get(2));
        System.out.println(test.get(1));
        System.out.println(test.get(4));

    }


    private int capacity;
    private int count;
    private LruNode st;
    private LruNode end;
    private Map<Integer, LruNode> lruNodeMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        lruNodeMap = new HashMap<>();
        this.st = new LruNode();
        this.end = new LruNode();
        end.prev = st;
        st.next = end;
    }

    public int get(int key) {
        LruNode lruNode = lruNodeMap.get(key);
        if (capacity == 0 || lruNode == null) {
            return -1;
        }
        Node node = lruNode.nodeMap.get(key);
        int val = node.val;
        lruNode.removeNode(node);

        LruNode next = lruNode.next;
        if (next.no != lruNode.no + 1) {
            add(lruNode);
            next = lruNode.next;
        }
        next.put(key, val);
        lruNodeMap.put(key, next);

        remove(lruNode);
        return val;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        LruNode lruNode = lruNodeMap.get(key);
        if (lruNode == null) {

            if (count == capacity) {

                Node next = st.next.nodeSt.next;
                lruNodeMap.remove(next.key);
                st.next.removeNode(next);
                remove(st.next);
            } else {
                count++;
            }
            lruNode = st.next;
            if (lruNode.no != 1) {
                add(st);
                lruNode = st.next;
            }
            lruNode.put(key, value);
            lruNodeMap.put(key, lruNode);
        } else {
            Node node = lruNode.nodeMap.get(key);
            lruNode.removeNode(node);

            LruNode next = lruNode.next;
            if (next.no != lruNode.no + 1) {
                add(lruNode);
                next = lruNode.next;
            }
            next.put(key, value);
            lruNodeMap.put(key, next);

            remove(lruNode);
        }
    }

    private void add(LruNode lruNode) {
        LruNode add = new LruNode();
        add.no = lruNode.no + 1;
        LruNode next = lruNode.next;
        lruNode.next = add;
        add.prev = lruNode;
        add.next = next;
        next.prev = add;
    }

    private void remove(LruNode lruNode) {
        if (lruNode.count == 0) {
            LruNode next = lruNode.next;
            LruNode prev = lruNode.prev;
            prev.next = next;
            next.prev = prev;
        }
    }

    class LruNode {
        public int no = 0;
        public int count = 0;
        public Node nodeSt;
        public Node nodeEnd;
        public LruNode next;
        public LruNode prev;

        private Map<Integer, Node> nodeMap;

        public LruNode() {
            this.nodeMap = new HashMap<>();
            this.nodeSt = new Node(0, 0);
            this.nodeEnd = new Node(0, 0);
            nodeEnd.prev = nodeSt;
            nodeSt.next = nodeEnd;
        }

        public void put(int key, int value) {
            Node node = new Node(key, value);
            putLast(node);
            count++;
            nodeMap.put(key, node);
        }

        public Node get(int key) {
            Node node = nodeMap.get(key);
            removeNode(node);
            return node;
        }

        private void putLast(Node node) {
            Node prev = nodeEnd.prev;
            prev.next = node;
            node.prev = prev;
            node.next = nodeEnd;
            nodeEnd.prev = node;
        }

        private void putHead(Node node) {

            Node next = nodeSt.next;
            nodeSt.next = node;
            node.prev = nodeSt;
            node.next = next;
            next.prev = node;
        }

        private void removeNode(Node node) {
            Node prev = node.prev;
            prev.next = node.next;
            node.next.prev = prev;
            nodeMap.remove(node.key);
            count--;
        }
    }

    class Node {
        public int key;
        public int val;
        public Node prev;
        public Node next;

        public Node() {
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }


}
